/*
 * @lc app=leetcode.cn id=85 lang=javascript
 *
 * [85] 最大矩形
 */

// @lc code=start
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function (matrix) {
  const m = matrix.length;
  if (m === 0) {
    return 0;
  }

  const n = matrix[0].length;
  const map = new Array(m).fill(0).map((_) => new Array(n).fill(0));
  // 计算连续1的最大长度
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === '1') {
        map[i][j] = (j === 0 ? 0 : map[i][j - 1]) + 1;
      }
    }
  }

  let result = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      let width = map[i][j];
      let area = width;
      let k = i - 1;
      // 以当前点位右下角，计算矩形面积
      while (k >= 0) {
        width = Math.min(width, map[k][j]);
        area = Math.max(area, (i - k + 1) * width);
        k--;
      }
      result = Math.max(result, area);
    }
  }

  return result;
};
// @lc code=end
